package priv.sort.heap;

import priv.sort.util.SortUtil;

public class HeapSort {
    private static int len;

    public static void sort(int[] arr) {
        len = arr.length;
        // 构建大顶堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            modifyHeap(arr, i);
        }
        // 堆排序
        for (int i = len - 1; i > 0; i--) {
            // 交换堆顶元素和最后一个元素
            SortUtil.swap(arr, 0, len - 1);
            len--;
            // 调整堆
            modifyHeap(arr, 0);
        }
    }

    private static void modifyHeap(int[] arr, int index) {
        // index节点的左孩子和右孩子
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        // 较大的节点
        int largest = index;
        // 找出左右孩子中较大的节点
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }
        // 如果largest不是index节点，则交换
        if (largest!= index) {
            SortUtil.swap(arr, index, largest);
            // 继续调整子树
            modifyHeap(arr, largest);
        }
    }
}